//
// Created by liushuai on 18-8-16.
//
#include <iostream>
using namespace std;

template <typename T>
class LinkNode {
 public:
  T data;
  LinkNode<T> *next;
  LinkNode<T>(const T value) : data(value), next(nullptr){};
  LinkNode<T>() : data(0), next(nullptr){};
  LinkNode(int info, LinkNode<T> *nextValue) {
    data = info;
    next = nextValue;
  }
};

template <typename T>
class LinkList {
 private:
  LinkNode<T> *head, *tail;
  LinkNode<T> *setPos(const int i);

 public:
  LinkList<T>() {
    // 头结点不参与计数
    head = new LinkNode<T>();
    tail = new LinkNode<T>();
  }
  ~LinkList<T>() {
    delete head;
    delete tail;
  }
  void CreateLinkList(int n);                      // 创建链表
  bool insert(const int position, const T value);  // 在指定位置插入结点
  void TraverseLinkList();                         // 遍历链表
  bool isEmpty();                                  // 判断链表是否为空
  int length();                                    // 链表长度
  bool Delete(int position);                       // 删除指定位置结点
  bool clear();                                    // 删除整个链表
  bool getPos(int &pos, const T value);
  bool getValue(const int ind, T &value);
  bool append(const T value);
};
template <typename T>
LinkNode<T> *LinkList<T>::setPos(const int i) {
  int count = 1;
  if (i == -1) {
    return head;
  } else {
    LinkNode<T> *p = head->next;
    while (p->next != nullptr && count < i) {
      p = p->next;
      count++;
    }
    return p;
  }
}
template <typename T>
void LinkList<T>::CreateLinkList(int n) {
  if (n < 0) {
    cout << "输入结点个数错误！" << endl;
  } else {
    LinkNode<T> *pnew, *ptemp;
    ptemp = head;
    int i = n;
    while (n-- > 0) {
      int info;
      cout << "输入第" << i - n << "个结点值：";
      cin >> info;
      pnew = new LinkNode<T>(info);
      ptemp->next = pnew;
      ptemp = pnew;
    }
  }
}
// postion从1开始计数，到链表长度加1结束，头结点后的结点称为第一个结点
template <typename T>
bool LinkList<T>::insert(int position, T value) {
  LinkNode<T> *p, *temp;
  // 获取position前一个节点
  p = setPos(position - 1);
  if (p == nullptr) {
    cout << "非法节点"
         << "\n";
    return false;
  } else {
    temp = new LinkNode<T>(value, p->next);
    p->next = temp;
    if (p == tail) {
      tail = temp;
    }
    return true;
  }
}
template <typename T>
void LinkList<T>::TraverseLinkList() {
  LinkNode<T> *p = head->next;
  while (p != nullptr) {
    cout << p->data << " ";
    p = p->next;
  }
  cout << endl;
}

template <typename T>
bool LinkList<T>::isEmpty() {
  if (head->next == nullptr)
    return true;
  else
    return false;
}
template <typename T>
int LinkList<T>::length() {
  LinkNode<T> *p = head->next;
  int n = 0;
  while (p != nullptr) {
    n++;
    p = p->next;
  }
  return n;
}
// position只能从1开始到链表长度结束
template <typename T>
bool LinkList<T>::Delete(int position) {
  if (position < 0 || position > length()) {
    cout << "输入位置错误！" << endl;
    exit(EXIT_FAILURE);
  } else {
    LinkNode<T> *ptemp = head, *pdelete;
    while (position-- > 1) ptemp = ptemp->next;
    pdelete = ptemp->next;
    ptemp->next = pdelete->next;
    delete pdelete;
    pdelete = nullptr;
  }
}
template <typename T>
bool LinkList<T>::clear() {
  LinkNode<T> *pdelete = head->next, *ptemp;
  while (pdelete != nullptr) {
    ptemp = pdelete->next;
    head->next = ptemp;
    delete pdelete;
    pdelete = ptemp;
  }
  return true;
}
// 获取元素value所在位置
template <typename T>
bool LinkList<T>::getPos(int &p, const T value) {
  LinkNode<T> *q = head;
  int pos = 0;
  while (q != nullptr) {
    q = q->next;
    pos++;
    if (q->data == value) {
      p = pos;
      return true;
    }
  }
  return false;
}
template <typename T>
bool LinkList<T>::getValue(const int p, T &value) {
  LinkNode<T> *q = head;
  int count = 0;
  while (q != nullptr) {
    q = q->next;
    count++;
    if (count == p) {
      value = q->data;
      return true;
    }
  }
  return false;
}
template <typename T>
bool LinkList<T>::append(const T value) {
  LinkNode<T> *q = head;
  LinkNode<T> *p = new LinkNode<T>(value);
  if (q == nullptr) {
    head = p;
    return false;
  } else {
    while (q->next != nullptr) {
      q = q->next;
    }
    q->next = p;
    return true;
  }
}
